#pragma once

#include <array>
#include <vector>

namespace solution_037
{

class Solution {
public:
    void solveSudoku(std::vector< std::vector<char> >& board)
    {
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] == '.')
                    continue;
                int i = board[r][c] - '1';
                int b = (r / 3) * 3 + (c / 3);
                m_row_checks[r * 9 + i] = true;
                m_col_checks[c * 9 + i] = true;
                m_box_checks[b * 9 + i] = true;
            }
        }
        backtrace(board, 0, 0);
    }

private:
    bool backtrace(std::vector< std::vector<char> >& board, int r, int c)
    {
        /* find an empty cell */
        while (r < 9 && board[r][c] != '.') {
            if (++c == 9) {
                ++r;
                c = 0;
            }
        }
        if (r == 9)
            return true;

        int b = (r / 3) * 3 + (c / 3);

        /* fill if found valid number or return otherwise */
        for (int i = 0; i < 9; ++i) {
            if ( m_row_checks[r * 9 + i] ||
                 m_col_checks[c * 9 + i] ||
                 m_box_checks[b * 9 + i] )
                continue;

            m_row_checks[r * 9 + i] = true;
            m_col_checks[c * 9 + i] = true;
            m_box_checks[b * 9 + i] = true;
            board[r][c] = '1' + i;

            if (backtrace(board, r, c))
                return true;

            board[r][c] = '.';
            m_row_checks[r * 9 + i] = false;
            m_col_checks[c * 9 + i] = false;
            m_box_checks[b * 9 + i] = false;
        }

        return false;
    }

    std::array<bool, 9 * 9> m_row_checks { false };
    std::array<bool, 9 * 9> m_col_checks { false };
    std::array<bool, 9 * 9> m_box_checks { false };
};

}  /* namespace solution_037 */
